package javatest.algorith;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;


public class MaxProfit {
    /**
     * 求多个项目的最大收益
     * @param args
     */
    public static void main(String[] args) {
        int k = 10;
        int startMoney = 10;
        int[] costs = {15,13,12,11,7,16,14,13,23,14,26,17};
        int[] profits = {2,3, 5, 6,3, 1, 4, 6, 7, 4, 2, 4};

        // int k = 3;
        // int startMoney = 10;
        // int[] costs = {15,13,12,11,7,16};
        // int[] profits = {2,3,5,6,3,1};

        MaxProfit m = new MaxProfit();
        System.out.println(m.maxProfit(k, startMoney, costs, profits));
    }

    public class CostCompare implements Comparator<Case> {
    
        @Override
        public int compare(Case case1, Case case2) {
            return case1.cost - case2.cost;
        }
    } 

    public class ProfitCompare implements Comparator<Case> {
    
        @Override
        public int compare(Case case1, Case case2) {
            return case2.profit - case1.profit;
        }
    }

    public int maxProfit(int k, int startMoney, int[] costs, int[] profits) {
        PriorityQueue<Case> costQ = new PriorityQueue<>(new CostCompare());
        PriorityQueue<Case> profitQ = new PriorityQueue<>(new ProfitCompare());
        Case c = null;
        for(int i=0;i<costs.length;i++){
            c = new Case(costs[i], profits[i]);
            costQ.add(c);
            // profitQ.add(c);
        }
        
        while(k > 0){
            while( !costQ.isEmpty() && costQ.peek().cost <= startMoney){
                profitQ.add(costQ.poll());
            }
            if (!profitQ.isEmpty()){
                startMoney += profitQ.poll().profit;
                k--;
            }else break;
        }

        return startMoney;
    }
    
    public void printResult(int k, int money, int[] costs, int[] profits, int expect, int result){
        System.out.println("项目次数k: " + k);
        System.out.println("startMoney: " + money);
        System.out.println("costs: " + Arrays.toString(costs));
        System.out.println("profits: " + Arrays.toString(profits));
        System.out.println("expect: " + expect);
        System.out.println("result: " + result);
        System.out.println();
    }
}

class Case {
    public int cost;
    public int profit;
    Case(int cost, int profit){
        this.cost = cost;
        this.profit = profit;
    }
}

